Notation polonaise inverse

Exemple d'utilisation de la pile en RPN

La notation polonaise inverse (NPI) (en anglais RPN pour Reverse Polish Notation), également connue sous le nom de notation post-fixée, permet d'écrire de façon non ambiguë les formules arithmétiques sans utiliser de parenthèses. Dérivée de la notation polonaise présentée en 1924 par le mathématicien polonais Jan Łukasiewicz, elle s’en différencie par l’ordre des termes, les opérandes y étant présentés avant les opérateurs et non l’inverse.

Par exemple, sur une calculatrice, l’expression $3\times (10+5)$ peut s'écrire en NPI sous la forme 10 Enter 5 + 3 x, ou encore sous la forme 3 Enter 10 Enter 5 + x.

Histoire

Friden EC-132, premier calculateur à utiliser la NPI.

Dérivée de la notation polonaise utilisée pour la première fois en 1924 par le mathématicien polonais Jan Łukasiewicz, la NPI a été inventée par le philosophe et informaticien australien Charles Leonard Hamblin (en) dans le milieu des années 1950, pour permettre les calculs sans faire référence à une quelconque adresse mémoire.

Un des premiers ordinateurs conçu, le Zuse 4 utilisait une pile, et une arithmétique de type NPI dès 1945, avant même que le concept soit formalisé. Puis d'autres ordinateurs comme le English Electric KDF9 ou le Burroughs B5000 en ont appliqué le principe dès 1963.

Mais la NPI se développera réellement sur les calculatrices, comme moyen de saisie interactif d'expression arithmétiques. Le premier calculateur électronique utilisant cette notation est la Friden (en) EC-132 en 1964.

C'est à la fin des années 1960, qu'elle a été diffusée dans le public comme interface utilisateur avec les calculatrices de bureau de Hewlett-Packard (HP-9100), puis avec la calculatrice scientifique HP-35 en 1972.

Implications pratiques

• l’écriture est raccourcie grâce à la suppression des parenthèses ;
• un résultat intermédiaire peut être réutilisé. Par exemple dans le calcul de ${\frac {\mathrm {sin} ({\frac {3\times \pi }{4}})}{\frac {3\times \pi }{4}}}$ on voit rapidement que l'expression ${\frac {3\times \pi }{4}}$ est utilisée deux fois. On peut la dupliquer dans la pile, ce qui donne :
  • 3 Enter π * 4 / DUP SIN SWAP / avec DUP et SWAP des opérateurs de pile pour dupliquer et intervertir.
• les calculs intermédiaires sont gérés sous forme de pile.
• parce qu'elle permet de voir les résultats intermédiaires, elle permet de détecter plus facilement les erreurs et donc un débogage plus rapide ; à l’époque des premiers circuits intégrés, cela en diminuait la complexité (gestion d'une pile et d'opérateurs de pile).
• ni l'opérateur, ni les parenthèses ne servant de séparateur, il faut en fournir entre deux opérandes successifs. Une espace devrait pouvoir suffire dans la majorité des cas ; sur une calculatrice, il s'agit de la touche Enter.

Quelques utilisations réelles de la NPI

Vidéo montrant la séquence de touches pour calculer huit fois six sur une calculatrice HP-32SII

• Le langage de programmation Forth
• Le langage de programmation RPL (Hewlett Packard)
• Le langage de programmation RPL/2
• Les calculatrices scientifiques Hewlett-Packard, dont les HP-35, HP-41, HP-28, HP-48, HP-15C, HP-35s, HP-12c, etc.
• Le langage de description de pages PostScript
• Le programme calc, intégré dans Emacs
• Le tableur d’Unix, le programme dc
• L’écriture d’interprètes^{[réf. nécessaire]}
• Le langage de description de format de bibliographie pour LaTeX et BibTex .bst.
• La création de graphiques complexes dans rrdtools.
• Le langage WarpScript, créé par Warp10 pour faciliter le traitement des Géo-Time Series (GTS).

Articles connexes

• Pile (informatique)
• Langue SVO
• Langue SOV
• Notations infixée, préfixée, polonaise et postfixée
• Algorithme Shunting-yard